package org.advanced.lru;

import java.util.HashMap;

/**
 * @author John.zhang
 * @version Id: LRUCache, v 1.0 2020/12/22 21:02 ZhiYong Exp $
 * 双向链表实现的LRU算法，这种算法相对于redis性能消耗偏大
 * redis内存上限设置
 * maxmemory
 * config set maxmemory 2GB
 * <p>
 * 数据淘汰算法配置
 * maxmemory-policy volatile-lru (设置了过期时间的最近最少使用的)
 * maxmemory-samples 5、10(随机采取几个数据，数字越大越精确) (随机采样淘汰法，热度最低的进行淘汰，通过server.lruclock (每隔100毫秒serverCron来更新这个戳)全局变量的一个时间戳来标记)
 * 热度评估：LRU的属性时间戳字段根其对比算出热度
 * <p>
 * 基于访问频率的淘汰机制 LFU
 * 标记key最后访问的时间、key被访问的计数器频率
 * lfu-log-factor 10 (控制计数器的频率)
 * lfu-decay-time 1 (分钟，间隔了多长时间没有被访问会递减)
 */
public class LruCache {
    /**
     * 链表容量
     */
    private HashMap<String, LruNode> map;
    /**
     * 链表容量
     */
    private int capacity;
    /**
     * 头结点
     */
    private LruNode head;
    /**
     * 尾节点
     */
    private LruNode tail;

    public void set(String key, Object value) {
        // 设置值，节被被访问时，移除节点，放到队头
        LruNode node = map.get(key);
        if (node != null) {
            node = map.get(key);
            node.value = value;
            remove(node, false);
        } else {
            node = new LruNode(key, value);
            if (map.size() >= capacity) {
                // 每次容量不足时先删除最久未使用的元素
                remove(tail, true);
            }
            map.put(key, node);
        }
        // 将刚添加的元素设置为head
        setHead(node);
    }

    /**
     * 取值，节被被访问时，移除节点，放到队头
     */
    public Object get(String key) {
        LruNode node = map.get(key);
        if (node != null) {
            // 将刚操作的元素放到head
            remove(node, false);
            setHead(node);
            return node.value;
        }
        return null;
    }

    /**
     * 将节点设置为头节点
     */
    private void setHead(LruNode node) {
        // 先从链表中删除该元素
        if (head != null) {
            node.next = head;
            head.prev = node;
        }
        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    /**
     * 从链表中删除此Node，需注意该Node是head或者是tail的情形
     */
    private void remove(LruNode node, boolean flag) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
        node.next = null;
        node.prev = null;
        if (flag) {
            map.remove(node.key);
        }
    }

    public LruCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<String, LruNode>();
    }

    /**
     * 链表中的节点
     */
    class LruNode {
        String key;
        Object value;
        LruNode prev;
        LruNode next;

        public LruNode(String key, Object value) {
            this.key = key;
            this.value = value;
        }
    }
}
